package ljl.alg.jianzhioffer.round3.hard;

/**
 * 这他妈不是世界上最难的题？
 */
public class _43_countDigitOne {

    /*
    输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
    输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
    1
    10 11 12 13 14 15 16 17 18 19
    21
    31
    41
    51
    61
    71
    81
    91

    100 101 102 103 104 105 106 107 108 109
    110 111 112 113 114 115 116 117 118 119
    121
    131
    141
    151   所有的 100 开头的，外加这些列出来的
    161
    171
    181
    191

    201   到 1000 都不会再出现这种情况，但是从 1000 开始，所有的数字都是 1 开头，都要算上，直到一万
    210 211 212 213 214 ... 219
    221
    231

    有一个变量叫 fuck_all 吧，10，100，1000，10000，每次 *10
    还有个变量，每个十位数都会导致出现一次 1，怎么算？
    fuck_all = 1, all = 0
    0-9: 1
    fuck_all = 10, all = 1
    10-99: fuck_all + 10 * all = 20
    fuck_all = 100, all = 20
    100-999: fuck_all + 10 * all = 300
    fuck_all = 1000, all = 300
    1000-9999: fuck_all + 10 * all = 4000

    我这个递推思路是对的，但是从哪停下来？
    我这个思路虽然沾了边，但是只沾了 1% 的边，沾的不是很边
    我这个思路是对的，但是解不出题来
     */

    public int countDigitOne(int n) {
        int digit = 1,
            low = 0,
            res = 0,
            high = n / 10,
            cur = n % 10;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                res += high * digit;
            } else if (cur == 1) {
                res += low + 1 + high * digit;
            } else {
                res += (high + 1) * digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }

}
